package binary_tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author Stark
 * @Date 2022/2/22 14:44
 */
public class BasicOperate {
    public static void main(String[] args) {
        TreeNode root = build();
        System.out.println("前序遍历的结果为:");
        preOrder(root);
        System.out.println();
        System.out.println("中序遍历的结果为:");
        inOrder(root);
        System.out.println();
        System.out.println("后序遍历的结果为:");
        postOrder(root);
        System.out.println("当前二叉树一共有:"+getNodes(root)+"个节点数");
        System.out.println("当前二叉树一共有:"+getNodesNonRecursion(root)+"个节点数");
        System.out.println("当前二叉树一共有:"+getLeafNodes(root)+"个叶子节点数");
        System.out.println("当前二叉树一共有:"+getLeafNodesNonRecursion(root)+"个叶子节点数");
        System.out.println(contains(root,'E'));
        System.out.println(contains(root,'P'));
        System.out.println("当前二叉树的高度为:"+height(root));
        System.out.println("当前二叉树第3层的节点个数为:"+getKLevelNodes(root,3));
    }
    public static TreeNode build() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeE.right = nodeH;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        return nodeA;
    }
    //先序遍历
    public static void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //后序遍历
    public static void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    //求节点个数
    public static int getNodes(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + getNodes(root.left) + getNodes(root.right);
    }
    //求结点个数的非递归
    public static int getNodesNonRecursion(TreeNode root){
        if(root == null){
            return 0;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            sum += size;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
        }
        return sum;
    }
    //求叶子节点的个数
    public static int getLeafNodes(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }
    //叶子结点的非递归
    public static int getLeafNodesNonRecursion(TreeNode root){
        if(root == null){
            return 0;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(node.left == null && node.right == null){
                    sum += 1;
                }
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
        }
        return sum;
    }
    //求第k层节点的个数
    public static int getKLevelNodes(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodes(root.left,k - 1) + getKLevelNodes(root.right,k - 1);
    }
    //查找节点
    public static boolean contains(TreeNode root,char ch){
        if(root == null){
            return false;
        }
        if(root.val == ch){
            return true;
        }
        return contains(root.left,ch) || contains(root.right,ch);
    }
    //求二叉树的高度
    public static int height(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + Math.max(height(root.left),height(root.right));
    }
}


class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(char val) { this.val = val; }
    TreeNode(char val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
